/**
 * 有一个带头结点的循环单链表,其结点均为正整数，设计一个算法，
 * 反复找出单链表中结点值最小的结点并输出，然后从该节点中删除，
 * 直到单链表为空，再删除头结点
 */

#include <stdio.h>
#include <stdlib.h>
#define bool int
#define true !0
#define false 0

//单向循环链表结构体定义
typedef struct LNode{
	struct LNode* next;		//后继指针
	int data;				//数据域
}LNode, *LinkedList;

bool core(LinkedList &list)
{
	LNode* node=list;				//遍历结点
	LNode* minNode=NULL;			//用来记录最小结点
	LNode* pre_min_node=list;		//记录当前最小结点的前驱结点
	LNode* pre_node;				//当前遍历链表的前驱结点
	LNode* delete_node=NULL;		//待删除的结点
	
	while(node->next!=list)
	{
		node=list->next;
		minNode=node;
		pre_min_node=list;
		while(node->next!=list)
		{
			if(node->data < minNode->data)
			{
				minNode=node;
				pre_min_node=pre_node;
			}
			pre_node=node;
			node=node->next;
		}
		printf("min node:%d\n",minNode->data);
		delete_node=minNode;
		//修改最小结点的前驱结点的next指向，指向minNode->next
		pre_min_node->next=minNode->next;
		//释放掉delete_node
		free(delete_node);
		//重置相关结点的指向
		node=node->next;
		minNode=node;
		pre_min_node=list;
		delete_node=NULL;
		pre_node=list;
	}
	
	//只剩下了头结点
	free(list);
	list=NULL;
	return true;
}